// Copyright 2018 gf Author(https://github.com/gogf/gf). All Rights Reserved.
//
// This Source Code Form is subject to the terms of the MIT License.
// If a copy of the MIT was not distributed with this file,
// You can obtain one at https://github.com/gogf/gf.

package gstr

// SimilarText calculates the similarity between two strings.
// See http://php.net/manual/en/function.similar-text.php.
func SimilarText(first, second string, percent *float64) int {
    var similarText func(string, string, int, int) int
    similarText = func(str1, str2 string, len1, len2 int) int {
        var sum, max int
        pos1, pos2 := 0, 0

        // Find the longest segment of the same section in two strings
        for i := 0; i < len1; i++ {
            for j := 0; j < len2; j++ {
                for l := 0; (i+l < len1) && (j+l < len2) && (str1[i+l] == str2[j+l]); l++ {
                    if l+1 > max {
                        max = l + 1
                        pos1 = i
                        pos2 = j
                    }
                }
            }
        }

        if sum = max; sum > 0 {
            if pos1 > 0 && pos2 > 0 {
                sum += similarText(str1, str2, pos1, pos2)
            }
            if (pos1+max < len1) && (pos2+max < len2) {
                s1 := []byte(str1)
                s2 := []byte(str2)
                sum += similarText(string(s1[pos1+max:]), string(s2[pos2+max:]), len1-pos1-max, len2-pos2-max)
            }
        }

        return sum
    }

    l1, l2 := len(first), len(second)
    if l1+l2 == 0 {
        return 0
    }
    sim := similarText(first, second, l1, l2)
    if percent != nil {
        *percent = float64(sim*200) / float64(l1+l2)
    }
    return sim
}
